/*
与面试题17.06 2出现的次数类似  我这里就只修改了判断条件的数字，其它的大致思路是差不多的
LC233.数字1的个数
难度：困难   2024.09.29
https://leetcode.cn/problems/number-of-digit-one/
*/

class Solution {
public:
    long k = 1000000000;
    int countDigitOne(int n) {
        if (n == 0)
            return {0};
        if (n < 10)
            return {1};
        int ans = 0, sum = 0;
        while (k > 0) {
            int d = n / k % 10;
            if (d < 1) {
                ans += sum * k;
            } else if (d == 1) {
                ans += sum * k + n % k + 1;
            } else {
                ans += (sum + 1) * k;
            }
            k /= 10;
            sum = sum * 10 + d;
        }
        return ans;
    }
};
